In recent years, various types of personal computers, such as desktop computers for use in offices and notebook computers for use in mobile environments, have been developed and marketed. Generally, these computer systems include main memory and an external storage device. The external storage device typically has a large memory capacity with a low storage capacity unit cost.
The external storage devices may be conventional hard disk drives (HDD) or floppy disk drives (FDD) that employ disk storage media. These disk storage devices typically provide large memory capacity at relatively low prices and operating costs, but may require highly delicate mechanical technology to perform various operations with a magnetic head, such as a disk seek operation. Accordingly, the disk storage devices may be easily damaged by physical impact and, therefore, may be considered less reliable than other types of memory devices.
In the past, external memory devices of the type that use semiconductor memory as a storage medium, such as SRAM (static random access memory) or DRAM (dynamic random access memory) have not provided a viable alternative to disk storage devices. Although semiconductor type external memory devices have faster processing speeds than disk access times and are less likely to be damaged upon physical impact, inherent drawbacks associated with SRAM and DRAM technology have prevented the use of SRAM and DRAM technology for mass storage.
In general, the price per memory capacity of SRAM is too high to make SRAM cost-effective for mass storage. Furthermore, the additional power required to save data held in DRAM typically increases the operating costs of the external storage device, and the power consumption associated with a DRAM refresh operation makes it difficult to implement DRAM in mobile environments where reduced power consumption is typically desirable.
On the other hand, external semiconductor memory devices that are implemented with flash memory, such as flash EEPROM (electrically erasable read-only-memory) provides a viable alternative to disk storage devices in certain applications. Flash memory devices are non-volatile memory devices that may be programmed more than once. Furthermore, flash memory devices have a simple structure that may be easily implemented. Because flash memory devices typically have low power consumption, are compact and light, and are less likely to be damaged from physical impact, they are often well suited for mobile environments, despite the trade-offs associated with flash memory devices. These trade-offs may include the requirement that an erase operation is performed prior to a programming (or re-write) operation, the requirement for a high voltage (e.g., 12V or 20V) to perform erase operations, and the requirement that a relative large memory unit that may include several KB to several hundreds of KB must be erased simultaneously.
A computer system (hereinafter also referred to as a “host”) accesses an external storage device by designating a logical address. The logical address refers to a position among a logical memory space which host software (i.e., an operating system or an application) recognizes, as compared to a physical storage location. Thus, a logical address is converted into a physical address corresponding to a physical memory space in the external storage device in order to access the addressed physical memory space.
Typically, an external storage device that uses flash memory requires additional software, referred to as disk emulation software, to ensure compatibility with the host during an access operation. Compatibility between the host and the external flash storage device during an access operation may be achieved by running a file system such as FTL (flash translation layer). In other words, the host recognizes the external flash memory device as HDD/SRAM and accesses the external flash memory device in the same manner as HDD/SRAM. The FTL connects a flash memory card to a file system that is used by an operating system on a PC and does not allow a write operation more than once (i.e. a re-write) at the same address without erasing the location prior to the re-write.
Functions of the FTL include logical-to-physical address mapping information management, bad block management, data preservation management due to unexpected power interruption, wearing management, and the like. A primary function of the FTL is a mapping technique. Mapping techniques are disclosed in U.S. Pat. No. 5,404,485 entitled “FLASH FILE SYSTEM”, U.S. Pat. No. 5,937,425 entitled “FLASH FILE SYSTEM OPTIMIZED FOR PAGE-MODE FLASH TECHNOLOGIES”, and U.S. Pat. No. 6,381,176 entitled “METHOD OF DRIVING REMAPPING IN FLASH MEMORY AND FLASH MEMORY ARCHITECTURE SUITABLE THEREFOF”, the disclosure of which is hereby incorporated herein by references.
Where a flash memory is accessed in block units, it is divided into a plurality of blocks. Numbers sequentially assigned to the divided blocks are called physical block numbers. A virtual number of a divided block, which a user recognizes, is called a logical block number. Methods for providing the mapping between the logical block number and the physical block number include a block mapping technique, a sector mapping technique, and a log mapping technique. In an FTL using a mapping technique, data of a logically continuous address may be stored at a physically different location. Because the unit of data in an erase operation is typically larger than the unit of data for write (or program) operation, a flash memory typically requires an operation so that data that is not to be erased that is scattered at physically different locations is collected at (i.e. copied to) an empty block in the same address space if it is difficult to write data in any block. This operation is called a merge operation.
The merge operation using the above block, sector and log mapping techniques will be more fully described below. Prior to describing the merge operation, it is assumed that a flash memory is divided into a plurality of memory blocks and that each memory block includes a plurality of pages (or sectors). “PBN” indicates a physical block number, “PPN” indicates a physical page number, and “LPN” indicates a logical page number.